package week_7.homework;
//修改二叉查找树的链表实现，使其add操作使用一个递归算法。

import week_4.practice.ArrayUnorderedList;
import week_4.practice.UnorderedListADT;
import week_6.practice.jsjf.BinaryTreeNode;
import week_6.practice.jsjf.LinkedBinaryTree;
import week_7.jsjf.BinarySearchTreeADT;
import week_7.jsjf.exceptions.ElementNotFoundException;
import week_7.jsjf.exceptions.EmptyCollectionException;
import week_7.jsjf.exceptions.NonComparableElementException;

public class NewLinkedBinarySearchTree<T> extends LinkedBinaryTree<T> implements BinarySearchTreeADT<T> {

    /**
     创造一个空的搜索二叉树。
     */
    public  NewLinkedBinarySearchTree() {
        super();
    }

    /*创造一个含有特殊根元素的二叉查找树*/
    public  NewLinkedBinarySearchTree(T element) {
        super(element);

        if (!(element instanceof Comparable))
            throw new NonComparableElementException("LinkedBinarySearchTree");
    }

    /**
     * Adds the specified object to the binary search tree in the
     * appropriate position according to its natural order.  Note that
     * equal elements are added to the right.
     *根据其自然顺序往二叉查找树上添加特定元素，若元素相同就添加在
     */
    public void addElement(T element) {
        if (!(element instanceof Comparable))
            throw new NonComparableElementException("LinkedBinarySearchTree");

        Comparable<T> comparableElement = (Comparable<T>) element;

        if (isEmpty())
            root = new BinaryTreeNode<T>(element);
        else //根不为空的时候
        {
            if (comparableElement.compareTo(root.getElement()) < 0) {//当要插入的元素小于根的元素时
                if (root.getLeft() == null)
                    this.getRootNode().setLeft(new BinaryTreeNode<T>(element));
                else
                    addElement(element, root.getLeft());
            } else//comparableElement.compareTo(root.getElement()) > 0
            {//当要插入的元素大于根的元素时
                if (root.getRight() == null)
                    this.getRootNode().setRight(new BinaryTreeNode<T>(element));
                else
                    addElement(element, root.getRight());
            }
        }
        modCount++;
    }

    /**
     * Adds the specified object to the binary search tree in the
     * appropriate position according to its natural order.  Note that
     * equal elements are added to the right.
     *
     * @param element the element to be added to the binary search tree
     */
    private void addElement(T element, BinaryTreeNode<T> node) {
        Comparable<T> comparableElement = (Comparable<T>) element;

        if (comparableElement.compareTo(node.getElement()) < 0) {
            if (node.getLeft() == null)
                node.setLeft(new BinaryTreeNode<T>(element));
            else
                addElement(element, node.getLeft());
        } else {
            if (node.getRight() == null)
                node.setRight(new BinaryTreeNode<T>(element));
            else
                addElement(element, node.getRight());
        }
    }
//其add操作使用一个递归算法。
    public void addElement2(T element,BinaryTreeNode<T> node)
    {
        if(!(element instanceof Comparable))
            throw new NonComparableElementException("LinkedBinarySearchTree");

        Comparable<T> comparableElement  = (Comparable<T>)element;
        if(isEmpty())
            root = new BinaryTreeNode<T>(element);
        else{
            if(comparableElement.compareTo(node.element)<0)
            {
                if(node.getLeft()==null)
                    node.setLeft(new BinaryTreeNode<T>(element));
                else {
                    addElement2(element,node.getLeft());
                }
            }
            else
                if(comparableElement.compareTo(node.element)>0)
                {
                    if(node.getRight()==null)
                        node.setRight(new BinaryTreeNode<T>(element));
                    else
                    {
                        addElement2(element,node.getRight());
                    }
                }
        }


    }

    /**
     * @param targetElement 在二叉查找树中找到的特定元素
     * @throws ElementNotFoundException 如果特定元素没找到报异常
     */
    public T removeElement(T targetElement) throws ElementNotFoundException {
        T result = null;

        if (isEmpty())
            throw new ElementNotFoundException("LinkedBinarySearchTree");
        else {
            BinaryTreeNode<T> parent = null;
            if (((Comparable<T>) targetElement).equals(root.element)) {
                result = root.element;
                BinaryTreeNode<T> temp = replacement(root);
                if (temp == null)
                    root = null;
                else {
                    root.element = temp.element;
                    root.setRight(temp.right);
                    root.setLeft(temp.left);
                }

                modCount--;
            } else {
                parent = root;
                if (((Comparable) targetElement).compareTo(root.element) < 0)
                    result = removeElement(targetElement, root.getLeft(), parent);
                else
                    result = removeElement(targetElement, root.getRight(), parent);
            }
        }

        return result;
    }

    /**
     * Removes the first element that matches the specified target
     * element from the binary search tree and returns a reference to
     * it.  Throws a ElementNotFoundException if the specified target
     * element is not found in the binary search tree.
     *
     * @param targetElement 在二叉查找树中找到的特定元素
     * @param node          查找到的结点
     * @param parent        需要查找的结点的双亲及结点
     * @throws ElementNotFoundException 如果目标元素没有找到
     */
    private T removeElement(T targetElement, BinaryTreeNode<T> node, BinaryTreeNode<T> parent) throws ElementNotFoundException {
        T result = null;

        if (node == null)
            throw new ElementNotFoundException("LinkedBinarySearchTree");
        else {
            if (((Comparable<T>) targetElement).equals(node.element)) {
                result = node.element;
                BinaryTreeNode<T> temp = replacement(node);
                if (parent.right == node)
                    parent.right = temp;
                else
                    parent.left = temp;

                modCount--;
            } else {
                parent = node;
                if (((Comparable) targetElement).compareTo(node.element) < 0)
                    result = removeElement(targetElement, node.getLeft(), parent);
                else
                    result = removeElement(targetElement, node.getRight(), parent);
            }
        }

        return result;
    }

    /**
     * @param node the node to be removed
     * @return a reference to the replacing node
     */
    //Replacement方法返回一个结点的引用，该结点将要代替要删除的结点。
    private BinaryTreeNode<T> replacement(BinaryTreeNode<T> node) {
        BinaryTreeNode<T> result = null;
        //如果被删除结点没有孩子，则返回null
        if ((node.left == null) && (node.right == null))
            result = null;
            //如果被删除结点只有一个孩子，则返回这个孩子
        else if ((node.left != null) && (node.right == null))
            result = node.left;

        else if ((node.left == null) && (node.right != null))
            result = node.right;
            //如果被删除结点有两个孩子，则返回中序后继者（因为相等元素会放到右边）
        else {
            BinaryTreeNode<T> current = node.right;
            BinaryTreeNode<T> parent = node;

            while (current.left != null) {//右子树的左子树不为空的话
                parent = current;//将parent结点指向原结点的右子树
                current = current.left;//将current指向原结点的右子树的左子树
            }
            current.left = node.left;//
            if (node.right != current) {
                parent.left = current.right;
                current.right = node.right;
            }

            result = current;//最后返回的是current。
        }

        return result;
    }

    /**
     * Removes elements that match the specified target element from
     * the binary search tree. Throws a ElementNotFoundException if
     * the sepcified target element is not found in this tree.
     *
     * @param targetElement the element being sought in the binary search tree
     * @throws ElementNotFoundException if the target element is not found
     */
    public void removeAllOccurrences(T targetElement)
            throws ElementNotFoundException {
        removeElement(targetElement);

        try {
            while (contains((T) targetElement))
                removeElement(targetElement);
        } catch (Exception ElementNotFoundException) {
        }
    }

    /**
     * Removes the node with the least value from the binary search
     * tree and returns a reference to its element.  Throws an
     * EmptyCollectionException if this tree is empty.
     *
     * @return a reference to the node with the least value
     * @throws EmptyCollectionException if the tree is empty
     */
    public T removeMin() throws EmptyCollectionException {
        T result = null;

        if (isEmpty())
            throw new EmptyCollectionException("LinkedBinarySearchTree");
        else {
            if (root.left == null) {
                result = root.element;
                root = root.right;
            } else {
                BinaryTreeNode<T> parent = root;
                BinaryTreeNode<T> current = root.left;
                while (current.left != null) {
                    parent = current;
                    current = current.left;
                }
                result = current.element;
                parent.left = current.right;
            }

            modCount--;
        }

        return result;
    }

    /**
     * Removes the node with the highest value from the binary
     * search tree and returns a reference to its element.  Throws an
     * EmptyCollectionException if this tree is empty.
     *
     * @return a reference to the node with the highest value
     * @throws EmptyCollectionException if the tree is empty
     */
    public T removeMax() throws EmptyCollectionException {
        T result = null;

        if (isEmpty())
            throw new EmptyCollectionException("LinkedBinarySearchTree");
        else {
            if (root.right == null) {
                result = root.element;
                root = root.left;
            } else {
                BinaryTreeNode<T> parent = root;
                BinaryTreeNode<T> current = root.right;
                while (current.right != null) {
                    parent = current;
                    current = current.right;
                }
                result = current.element;
                parent.right = current.left;
            }

            modCount--;
        }

        return result;
    }

    /**
     * Returns the element with the least value in the binary search
     * tree. It does not remove the node from the binary search tree.
     * Throws an EmptyCollectionException if this tree is empty.
     *
     * @return the element with the least value
     * @throws EmptyCollectionException if the tree is empty
     */
    public T findMin() throws EmptyCollectionException {
        T result = null;

        if (isEmpty())
            throw new EmptyCollectionException("LinkedBinarySearchTree");
        else {
            if (root.left == null) {
                result = root.element;
            } else {
                BinaryTreeNode<T> parent = root;
                BinaryTreeNode<T> current = root.left;
                while (current.left != null) {
                    parent = current;
                    current = current.left;
                }
                result = current.element;
            }
        }
        return result;
    }

    /**
     * Returns the element with the highest value in the binary
     * search tree.  It does not remove the node from the binary
     * search tree.  Throws an EmptyCollectionException if this
     * tree is empty.
     *
     * @return the element with the highest value
     * @throws EmptyCollectionException if the tree is empty
     */
    public T findMax() throws EmptyCollectionException {
        T result = null;

        if (isEmpty())
            throw new EmptyCollectionException("LinkedBinarySearchTree");
        else {
            if (root.right == null) {
                result = root.element;
            } else {
                BinaryTreeNode<T> parent = root;
                BinaryTreeNode<T> current = root.right;
                while (current.right != null) {
                    parent = current;
                    current = current.right;
                }
                result = current.element;
            }
        }
        return result;
    }


    /**
     * Returns the left subtree of the root of this tree.
     *
     * @return a link to the left subtree fo the tree
     */
    public LinkedBinarySearchTree<T> getLeft() {
        if (root == null) {
            throw new week_6.practice.jsjf.exceptions.EmptyCollectionException("BinaryTree");
        }
        LinkedBinarySearchTree<T> result = new LinkedBinarySearchTree<>();
        result.root = root.getLeft();
        return result;
    }

    /**
     * Returns the right subtree of the root of this tree.
     *
     * @return a link to the right subtree of the tree
     */
    public LinkedBinarySearchTree<T> getRight() {
        if (root == null) {
            throw new week_6.practice.jsjf.exceptions.EmptyCollectionException("BinaryTree");
        }
        LinkedBinarySearchTree<T> result = new LinkedBinarySearchTree<>();
        result.root = root.getRight();
        return result;
    }


    public T find(T targetElement) throws ElementNotFoundException {
        BinaryTreeNode<T> current = findNode(targetElement,root);
        if (current == null)
            throw new week_6.practice.jsjf.exceptions.ElementNotFoundException("LinkedBinaryTree");

        return (current.getElement());
    }

    private BinaryTreeNode<T> findNode(T targetElement, BinaryTreeNode<T> next) {
        if (next == null)
            return null;

        if (next.getElement().equals(targetElement))
            return next;

        BinaryTreeNode<T> temp = findNode(targetElement, next.getLeft());

        if (temp == null)
            temp = findNode(targetElement, next.getRight());

        return temp;
    }
public String toString()
{
    UnorderedListADT<BinaryTreeNode<T>> nodes = new ArrayUnorderedList<BinaryTreeNode<T>>();
    UnorderedListADT<Integer> levelList = new ArrayUnorderedList<Integer>();
    BinaryTreeNode<T> current;
    String result = "";
    int printDepth = this.getHeight();
    int possibleNodes = (int)Math.pow(2, printDepth + 1);
    int countNodes = 0;

    nodes.addToRear(root);
    Integer currentLevel = 0;
    Integer previousLevel = -1;
    levelList.addToRear(currentLevel);

    while (countNodes < possibleNodes)
    {
        countNodes = countNodes + 1;
        current = nodes.removeFirst();
        currentLevel = levelList.removeFirst();
        if (currentLevel > previousLevel)
        {
            result = result + "\n\n";
            previousLevel = currentLevel;
            for (int j = 0; j < ((Math.pow(2, (printDepth - currentLevel))) - 1); j++)
                result = result + " ";
        }
        else
        {
            for (int i = 0; i < ((Math.pow(2, (printDepth - currentLevel + 1)) - 1)) ; i++)
            {
                result = result + " ";
            }
        }
        if (current != null)
        {
            result = result + (current.getElement()).toString();
            nodes.addToRear(current.getLeft());
            levelList.addToRear(currentLevel + 1);
            nodes.addToRear(current.getRight());
            levelList.addToRear(currentLevel + 1);
        }
        else {
            nodes.addToRear(null);
            levelList.addToRear(currentLevel + 1);
            nodes.addToRear(null);
            levelList.addToRear(currentLevel + 1);
            result = result + " ";
        }

    }

    return result;
}
}
